package listbyorder.access001_100.test52;

import java.util.ArrayList;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/1 16:18
 */
public class Solution1 {

    // 定义一个全局变量
    int ans = 0;

    public int totalNQueens(int n) {
        dfs(new ArrayList<Integer>(), n);
        return ans;
    }

    private void dfs(ArrayList<Integer> path, int n) {
        if (path.size() == n) {
            ans++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!path.contains(i)) {
                // 当前的列在之前的path中没有出现过，才会加入到当前的path
                if (!path.contains(i)) {
                    // 判断当前是否满足对角线上的元素满足条件
                    if (isXsite(path, i)) {
                        path.add(i);
                        dfs(path, n);
                        path.remove(path.size() - 1);
                    }
                }
            }
        }
    }

    private boolean isXsite(ArrayList<Integer> path, int cur) {
        if (path == null) return true;
        int size = path.size();
        for (int i = 0; i < path.size(); i++) {
            if (Math.abs(cur - path.get(i)) == size - i) {
                return false;
            }
        }
        return true;
    }
}
